home *** CD-ROM | disk | FTP | other *** search
/ Aminet 5 / Aminet 5 - March 1995.iso / Aminet / dev / misc / LEDA_gene.lha / LEDA-3.1c-generic / incl / LEDA / partition.h < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-05  |  2.2 KB  |  108 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  partition.h
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #ifndef LEDA_PARTITION_H
  17. #define LEDA_PARTITION_H
  18.  
  19. //------------------------------------------------------------------------------
  20. // partition   (union find)
  21. //------------------------------------------------------------------------------
  22.  
  23. #include <LEDA/basic.h>
  24.  
  25.  
  26. class partition_node {
  27.  
  28. friend class partition;
  29.  
  30. partition_node* father;
  31. partition_node* next;
  32. int size;
  33. GenPtr info;
  34.  
  35. public:
  36.  
  37. partition_node(GenPtr x, partition_node* n)  
  38. { 
  39.   father=0; size=1; info=x; next = n; 
  40.  }
  41.  
  42.   LEDA_MEMORY(partition_node)
  43.  
  44. };
  45.  
  46.  
  47. // a partition item is a pointer to a partition node:
  48.  
  49. typedef partition_node* partition_item;
  50.  
  51.  
  52.  
  53. class partition {
  54.  
  55. virtual void clear_inf(GenPtr&) const {}
  56.  
  57. partition_item used_items;                 // List of used partition items
  58.  
  59. public:  // operations 
  60.  
  61. void  union_blocks(partition_item,partition_item);
  62. partition_item find(partition_item);
  63.  
  64. partition_item make_block(GenPtr x = nil) 
  65. { used_items = new partition_node(x,used_items); 
  66.   return used_items; 
  67.  }
  68.  
  69. int  same_block(partition_item a, partition_item b) 
  70. { return find(a)==find(b); }
  71.  
  72. GenPtr   inf(partition_item a) { return find(a)->info; }
  73.  
  74. void  set_inf(partition_item a, GenPtr x) { find(a)->info = x; }
  75.  
  76. void clear();                      // deletes all used items
  77.  
  78. partition() { used_items = 0; }  
  79. virtual ~partition() { clear(); }
  80.  
  81. };
  82.  
  83.  
  84. //------------------------------------------------------------------------------
  85. // PARTITION  (named partitions)
  86. //-----------------------------------------------------------------------------
  87.  
  88. template <class type>
  89.  
  90. class PARTITION : public partition {
  91.  
  92. void clear_inf(GenPtr& x) const { Clear(ACCESS(type,x)); }
  93.  
  94. public:
  95.  
  96. partition_item make_block(type x) { return partition::make_block(Convert(x)); }
  97.  
  98. type  inf(partition_item a)       { return (type)partition::inf(a); }
  99.  
  100. void  set_inf(partition_item a, type x) { partition::set_inf(a,Convert(x)); }
  101.  
  102.  PARTITION() {}
  103. ~PARTITION() {}
  104. };
  105.  
  106.  
  107. #endif
  108.